﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions.Problems
{
    /*
     * Let S(A) represent the sum of elements in set A of size n. We shall call it a special sum set if for any two non-empty disjoint subsets, B and C, the following properties are true:

    S(B) ≠ S(C); that is, sums of subsets cannot be equal.
    If B contains more elements than C then S(B) > S(C).

For this problem we shall assume that a given set contains n strictly increasing elements and it already satisfies the second rule.

Surprisingly, out of the 25 possible subset pairs that can be obtained from a set for which n = 4, only 1 of these pairs need to be tested for equality (first rule). Similarly, when n = 7, only 70 out of the 966 subset pairs need to be tested.

For n = 12, how many of the 261625 subset pairs that can be obtained need to be tested for equality?

NOTE: This problem is related to problems 103 and 105.

     * */
    class Problem106 : IProblem
    {
        public string Calculate()
        {
            long valid = 0;

            for (int i = 2; i <= 6; i++)
            {
                valid += CommonFunctions.CalculateBinome(12, 2 * i) * ValidTests(i);
            }


            return valid.ToString();
        }




        int ValidTests(int subsetSize)
        {
            //ako je subset 2 znači da gledamo u skupinama od po četiri elementa kombinacije
            //za subset 2 ima samo jedna
            if (subsetSize < 2)
                return 0;
            if (subsetSize == 2)
                return 1;

            //za subset 3 ih ima pet, ali brojat ćemo ih na način da tražimo sve kombinacije na skup od 2n veličine n

            List<int> set = new List<int>();
            for (int i = 0; i < subsetSize * 2 - 1; i++)
            {
                set.Add(i);
            }

            var combinations = CommonFunctions.GetCombinationList(set, subsetSize);

            int valid = 0;

            foreach (var combination in combinations)
            {
                int counter = 1;

                foreach (int i in set)
                {
                    if (combination.Contains(i))
                        counter--;
                    else
                        counter++;

                    if (counter < 0)
                        break;
                }

                if (counter < 0)
                    valid++;


            }

            return valid;
        }
    }
}
